#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

//Q5
//
#define vItr vector<int>::const_iterator
int minVectorInt(vItr start, vItr end){ 
	vItr mid = start+((end-start)/2);
	if(start == end)
		return INT_MAX;
	else{
		int midInt = *(mid);
		int left = minVectorInt(start, mid);
		int right = minVectorInt(mid+1,end);
		int lrmin = left < right ? left : right;
		return (midInt < lrmin ? midInt : lrmin);
	}
}

int minVectorInt(const vector<int>& a){
	return minVectorInt(a.begin(), a.end());
}

//Q6

template<class RandItr>
void mergeSort(RandItr tmp, RandItr start, RandItr end){	
	if(start+1 < end){
		//find center
		int size = end - start;
		int halfSize = size/2;
		RandItr center = start + halfSize;
		cout << "c: " << *center <<endl;
		//sort left
		mergeSort(tmp, start, center);
		//sort right
		mergeSort(tmp, center, end);
		//merge the two
		merge(start, center, center, end, tmp);
		copy(tmp, tmp+size, start);
	}
}

template <class RandItr>
void mergeSort( RandItr start, RandItr end ){
	int sz = end-start; // or use auto sz = end-start;
	typedef typename iterator_traits<RandItr>::value_type Object; //Xcode
	// typedef iterator_traits<RandItr>::value_type Object; //Other compilers
	// Don't worry about this line of code
	vector<Object> tmp(sz);
	mergeSort(tmp.begin(), start, end);
}

//Q7

class student{
	private:
		string name;
		double gpa;
	public:
		student(const string& name, double gpa) : name(name), gpa(gpa) {}
		string get_name(){
			return name;
		}
		double get_gpa(){
			return gpa;
		}
		bool operator<(const student& rhs){
			return name <rhs.name;
		}
};

class meFirst{
	string me;
	public:
	meFirst(const string& str) : me(str) {}
	bool operator()(student A, student B){
		if(A.get_name() == me)
			return true;
		if(B.get_name() == me)
			return false;
		return A < B;
	}
};

int main(){
	vector<int> nums = {10, 20, 1, 2, 1000, 100};
	mergeSort(nums.begin(), nums.end());
	for(int x : nums){
		cout << x << " ";
	}
	cout << endl;

	vector<student> studs;
	studs.push_back(student("john", 9.999));
	studs.push_back(student("brandon", 1.2356));
	studs.push_back(student("scott", 10000));

	sort(studs.begin(), studs.end(), meFirst("scott"));

	for(student x : studs){
		cout << x.get_name() << endl;
	}
}
